/**
 *
 */
package datastructure.sort;

import java.util.Comparator;

/**
 * Description：堆排序
 * Author: zhangc
 * Date：2017/6/19 21:13
 */
public final class HeapSort {

    // 堆排序，依次移除树的头结点
    public static <T extends Comparable<? super T>> void heapSort(T[] array) {
        T temp;
        constructHeap(array, array.length);
        for (int i = array.length - 1; i > 0; i--) {
            temp = array[ i ];
            array[ i ] = array[ 0 ];
            array[ 0 ] = temp;
            constructHeap(array, i);
        }
    }

    // 从非叶节点开始调整堆，直到最大或最小元素调整为 树的头结点
    private static <T extends Comparable<? super T>> void constructHeap(T[] array, int size) {
        int index = (size >> 1);
        for (; index >= 0; index--) {
            adjustHeap(array, index, size);
        }
    }


    // 递归的 调整堆，只调整堆中的一个节点
    private static <T extends Comparable<? super T>> void adjustHeap(T[] array, int index, int size) {
        int leftChild = (index << 1) + 1;
        int rightChild = (index << 1) + 2;
        int maxIndex = index;
        T temp;
        if (index <= (size >> 1)) {
            if (leftChild < size) {
                if (array[ maxIndex ].compareTo(array[ leftChild ]) < 0) {
                    maxIndex = leftChild;
                }
            }
            if (rightChild < size) {
                // 这里一定要是 array[maxIndex]
                if (array[ maxIndex ].compareTo(array[ rightChild ]) < 0) {
                    maxIndex = rightChild;
                }
            }

            if (maxIndex != index) {
                temp = array[ index ];
                array[ index ] = array[ maxIndex ];
                array[ maxIndex ] = temp;
                adjustHeap(array, maxIndex, size);
            }
        }
    }
}
